# -*- coding:utf-8 -*-
__author__ = 'gin.chen'


def quick_sort(data):
    __quick_sort(data, 0, len(data) - 1)


def __partition(data, l, r):
    v = data[l]
    j = l
    for i in range(l + 1, r + 1):
        if data[i] < v:
            j += 1
            data[i], data[j] = data[j], data[i]
    data[l], data[j] = data[j], data[l]
    return j


def __quick_sort(data, l, r):
    if l >= r:
        return
    p = __partition(data, l, r)
    __quick_sort(data, l, p - 1)
    __quick_sort(data, p + 1, r)


if __name__ == '__main__':
    a = [4, 3, 7, 8, 9, 1, 2, 0, 5]
    quick_sort(a)
    for i in a:
        print i

